package com.leetcode.algorithm.common;

/**
 * Quick Union 的「并查集」实现代码
 * +按秩合并
 * +路径压缩
 * 
 * @author jie.deng
 *
 */
public class UnionFind06 {
	// 实际存储的是parent
	int roots[];
	// 存储的是高度
	int ranks[];
	int count;

	public UnionFind06(int size) {
		roots = new int[size];
		ranks = new int[size];
		for (int i = 0; i < size; i++) {
			roots[i] = i;
			ranks[i] = 1;
		}
		count = size;
	}

	private int findRoot(int x) {
		if (x == roots[x]) {
			return x;
		}
		// 路径压缩
		return x = findRoot(roots[x]);
	}

	public void union(int x, int y) {
		int rootX = findRoot(x);
		int rootY = findRoot(y);
		// 按秩合并
		if (rootX != rootY) {
			if (ranks[rootX] > ranks[rootY]) {
				roots[rootY] = rootX;
			} else if (ranks[rootX] < ranks[rootY]) {
				roots[rootX] = rootY;
			} else {
				roots[rootY] = rootX;
				ranks[rootX]++;
			}
		}
		count--;
	};

	public boolean isConnected(int x, int y) {
		return findRoot(x) == findRoot(y);
	}
}